package leecode;

import java.util.*;

/**
 * 第十七天
 */

public class LeetCode17 {
    //第二题
    //用大顶堆+小顶堆方法，可以看作大顶堆是普通班，小顶堆是实验班。数量上时刻保持 小顶-大顶<=1（两堆相等或者小顶比大顶多一个）。
    //
    //新学生先入普通班（大顶堆），此时可能会失去平衡了，于是取大顶堆的第一个（班里最好的学生）加入实验班（小顶堆）
    // 判断若数量过多（不是等于或多一个），取第一个（实验班里最差的学生）到普通班（大顶堆）里。
    // 取中位数的时候，若两堆数量相等，则各取堆顶取平均，若小顶比大顶多一，则多的那一个就是中位数。
    PriorityQueue<Integer>priorityQueue1;//左堆放刚进来的数据
    PriorityQueue<Integer>priorityQueue2;//右堆放从左堆来的数据
    public LeetCode17() {
        priorityQueue1=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        priorityQueue2=new PriorityQueue<>();
    }

    public void addNum(int num) {
        priorityQueue1.add(num);
        priorityQueue2.add(priorityQueue1.poll());
        if(priorityQueue1.size()+1<priorityQueue2.size()){
            priorityQueue2.add(priorityQueue1.poll());
        }
    }

    public double findMedian() {
        if((priorityQueue2.size()+priorityQueue1.size())%2!=0){
            return priorityQueue2.peek();
        }else {
            return (double) (priorityQueue1.peek()+priorityQueue2.peek())/2;
        }

    }
    //第一题利用快排解决
    public int prive(int[]arr,int l,int r){
        int tmp = arr[l];
        while (l<r) {

            while (r > l && arr[r] >= tmp) {
                r--;
            }
            arr[l] = arr[r];
            while (l < r && arr[l] <= tmp) {
                l++;
            }
            arr[r] = arr[l];
        }
        arr[l]=tmp;
        return l;
    }
    public void fast_sort(int[] arr,int l,int r){
        if (l>=r){
            return;
        }
        int k=prive(arr,l,r);
        fast_sort(arr,l,k-1);
        fast_sort(arr,k+1,r);
    }
    public  int[] getLeastNumbers(int[] arr, int k) {
        fast_sort(arr,0,arr.length-1);
        int[]arr1=new int[k];
        for (int i = 0; i < k; i++) {
            arr1[i]=arr[i];
        }
        return arr1;
    }

    public static void main(String[] args) {
        int[]arr={0,1,2,1};
        LeetCode17 leetCode17=new LeetCode17();
        leetCode17.getLeastNumbers(arr,2);
    }
}
